/*
 * @lc app=leetcode.cn id=977 lang=cpp
 *
 * [977] 有序数组的平方
 *
 * https://leetcode-cn.com/problems/squares-of-a-sorted-array/description/
 *
 * algorithms
 * Easy (69.24%)
 * Likes:    460
 * Dislikes: 0
 * Total Accepted:    276.4K
 * Total Submissions: 399.4K
 * Testcase Example:  '[-4,-1,0,3,10]'
 *
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 * 
 * 
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [-4,-1,0,3,10]
 * 输出：[0,1,9,16,100]
 * 解释：平方后，数组变为 [16,1,0,9,100]
 * 排序后，数组变为 [0,1,9,16,100]
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [-7,-3,2,3,11]
 * 输出：[4,9,9,49,121]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 10^4
 * -10^4 
 * nums 已按 非递减顺序 排序
 * 
 * 
 * 
 * 
 * 进阶：
 * 
 * 
 * 请你设计时间复杂度为 O(n) 的算法解决本问题
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        //先平方 后快排
        // for(int i = 0; i < nums.size(); i++){
        //     nums[i] *= nums[i];
        // }
        // sort(nums.begin(), nums.end());
        // return nums;

        // //双指针法
        // int size = nums.size();
        // int k = size-1;
        // int i = 0, j = size-1;
        // vector<int> result(size,0);
        // for(i; i <= j;  ){
        //     if(nums[i]*nums[i] < nums[j] * nums[j]) {
        //         result[k--] = nums[j] * nums[j];
        //         j--;
        //     }else{
        //         result[k--] = nums[i] * nums[i];
        //         i++;
        //     }
        // }
        // return result;


        // 双指针
        int front = 0;
        int back = nums.size()-1;
        int index = nums.size()-1;
        vector<int> res(nums.size(), 0);
        while(front <= back) {
            if(nums[front]*nums[front] < nums[back]*nums[back]) {
                res[index--] = nums[back] * nums[back];
                back--;
            } else {
                res[index--] = nums[front] * nums[front];
                front++;
            }
        }
        return res;


    }
};
// @lc code=end

